package monotonic_stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Class84 {
//
//    public int largestRectangleArea(int[] heights) {
//        if (heights.length==1){
//            return  heights[0];
//        }
//
//        if (heights.length==2){
//            int h=Math.min(heights[0],heights[1] );
//            return   h*2;
//        }
//
//        Deque<Integer> stack = new LinkedList();
//        stack.push(0);
//
//        for (int index = 1; index <heights.length ; index++) {
//            if (heights[index] >heights[stack.peek()]){
//                stack.push(index);
//            }else  if (heights[index]==heights[stack.peek()]){
//                stack.pop();
//                stack.push(index);
//            }else {
//                while (!stack.isEmpty()&&heights[index]<heights[stack.peek()]){
//                    if (!stack.isEmpty()){
//
//
//                    }
//                }
//
//
//
//            }
//
//
//        }
//
//    }

    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;

        st.push(0);
        int result = 0;
        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop(); // 这个可以加，可以不加，效果一样，思路不同
                st.push(i);
            } else {
                while (heights[i] < heights[st.peek()]) { // 注意是while
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    }








    public static void main(String[] args) {
        Class84 class84 = new Class84();
        int[] arr={2,1,5,6,2,3};
        System.out.println(class84.largestRectangleArea(arr));
    }

}
